//
// Created by ade on 2022/9/9.
//

/*
 * 					  0
			 1                  2
		3      	  4   	   5		  6
   7   		8   9   10  11   12    13   14
15  16   17  18

 * */

#include <iostream>
#include <vector>


using namespace std;

void make_max_heap(vector<int> &nums, int end) {
    while (end > 0) {
        int mid = (end - 1) / 2;
        int left = mid * 2 + 1;
        if (left <= end && nums[mid] < nums[left]) {
            swap(nums[mid], nums[left]);
        }
        int right = mid * 2 + 2;
        if (right <= end && nums[mid] < nums[right]) {
            swap(nums[mid], nums[right]);
        }
        end -= 2;
    }
}

void heap_sort(vector<int> &nums) {
    int len = nums.size();
    cout << "len:" << len << endl;
    for (int i = len - 1; i >= 0; i--) {
        make_max_heap(nums, i);

        if(i == len - 1){
            cout << "nums[0]:" << nums[0] << endl;
            break;
        }
        swap(nums[i], nums[0]);

    }
}

int main() {
    vector<int> nums = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
    heap_sort(nums);
    for (auto i : nums) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}